home *** CD-ROM | disk | FTP | other *** search
/ Group 42-Sells Out! - The Information Archive / Group 42 Sells Out (Group 42) (1996).iso / crypto / ladderde.txt < prev    next >
Text File  |  1995-11-30  |  11KB  |  290 lines
  1.                     Ritter Software Engineering
  2.                         2609 Choctaw Trail
  3.                         Austin, Texas 78745
  4.                  (512) 892-0494, ritter@cactus.org
  5.  
  6.  
  7.  
  8.           Ladder-DES: A Proposed Candidate to Replace DES
  9.  
  10.                            Terry Ritter
  11.                          February 22, 1994
  12.  
  13.  
  14.  Introduction
  15.  
  16.  Data enciphered by DES, the US Data Encryption Standard, has become
  17.  vulnerable to modern technical attacks.  Currently, such attacks
  18.  require substantial capital and high-tech engineering development
  19.  to produce a special "DES breaking" machine.  However, once such a
  20.  machine is built, attacks would become relatively fast and cheap.
  21.  Businesses which currently protect very expensive and marketable
  22.  secrets with DES should take immediate notice.
  23.  
  24.  To maintain earlier levels of security, DES must be replaced with
  25.  a stronger cipher.  The one obvious alternative to DES is a simple
  26.  construct built from DES called triple-DES.  Triple-DES, while
  27.  generally being thought of as "strong enough," also carries the
  28.  baggage of requiring three times the processing of normal DES.
  29.  
  30.  Because every security system is required to provide more benefit
  31.  than its cost, raising costs by a factor of three (when compared
  32.  to the alternative of normal DES) is a significant issue.  Such
  33.  costs could dangerously delay the retirement of ordinary DES.
  34.  
  35.  
  36.  Requirements
  37.  
  38.  The goal of this sequence of designs is to identify one or more
  39.  better candidates to replace DES.  Obviously, the first requirement
  40.  is that each candidate be substantially "stronger" than normal DES.
  41.  One problem here is that we can only _argue_ strength, so it is
  42.  important that candidate designs be openly presented and reviewed.
  43.  We cannot expect that most proposals will withstand such review.
  44.  
  45.  The second requirement is that each candidate design also be faster
  46.  than triple-DES; otherwise, we might just as well use triple-DES
  47.  and be done with it.  Speed is a measurable design quantity.
  48.  
  49.  My third requirement is to include operation on data blocks larger
  50.  than the 8-byte DES block.  Although DES is not normally used in a
  51.  way which is conducive to "dictionary" attack, such attacks could be
  52.  effective on the bare cipher itself.  This raises the possibility
  53.  that a "certificational" weakness may exist which we currently do
  54.  not know how to exploit, but which may be dangerous anyway.  This
  55.  particular weakness depends upon small blocks.
  56.  
  57.  At this point there is still some question as to whether it is
  58.  _possible_ to come up with candidate designs which meet these
  59.  three requirements.
  60.  
  61.  
  62.  Ladder Diagrams
  63.  
  64.  DES itself is frequently shown in figures which are described as
  65.  "ladder diagrams" because of their appearance:
  66.  
  67.                     |
  68.                     v
  69.            Initial Permutation
  70.                     v
  71.               <-- SPLIT -->
  72.              |             |
  73.              |      k1     |
  74.              v      v      |
  75.             XOR <-- f -----|
  76.              |             |
  77.              |      k2     |
  78.              |      v      v
  79.              |----- f --> XOR
  80.              |             |
  81.                   . . .
  82.  
  83.              |      k16    |
  84.              |      v      v
  85.              |----- f --> XOR
  86.              |             |
  87.              |             |
  88.              --> COLLECT <--
  89.                     v
  90.              Inv. Init. Perm.
  91.                     |
  92.                     v
  93.  
  94.  This is the data-transformation part of DES.  Not shown is the
  95.  key-schedule computation which produces k1 through k16, the 48-bit
  96.  "round" keys.  Also not shown is the construction of function "f."
  97.  
  98.  It will later be interesting to note that in DES each 32-bit data
  99.  rail value is expanded to 48 bits, the XOR occurs with a 48-bit key,
  100.  and the result contracted to 32 bits in 6-bit to 4-bit substitutions
  101.  known as "S-boxes."
  102.  
  103.  
  104.  Ladder-DES
  105.  
  106.  Consider this simple construct which looks something like two
  107.  rungs or steps on a ladder:
  108.  
  109.              A              B
  110.              |      k1      |
  111.              v      v       |
  112.             XOR <- DES1 ----|
  113.              |              |
  114.              |      k2      |
  115.              |      v       v
  116.              |---- DES2 -> XOR
  117.              |              |
  118.              v              v
  119.              C              D
  120.  
  121.  A, B, C and D represent 8-byte blocks; k1 and k2 represent 56-bit
  122.  DES keys.  This enciphers two DES data blocks in two DES operations;
  123.  this is a data rate similar to normal DES.  It can be described as
  124.  working on a single large block composed of A and B.  Note that the
  125.  data paths are twice the size of those used in DES itself.
  126.  
  127.  Also note that the design is asymmetric:  While ciphertext block C
  128.  is a function of every bit in plaintext blocks A and B, as well as
  129.  every bit in key k1, ciphertext block D is _also_ a function of
  130.  key k2.
  131.  
  132.  
  133.  Known-Plaintext Attack on Two-Rung Ladder-DES
  134.  
  135.  With known-plaintext, we essentially have a single-DES complexity:
  136.  Since A is known and C is known, the output of DES1 is known.  Since
  137.  the input to DES1 is also known, to find k1 we just do a normal DES
  138.  search.
  139.  
  140.  Alternately, since B is known and D is known, the output of DES2 is
  141.  known.  Since the input to DES2 is also known, to find k2 we just do
  142.  a normal DES search.
  143.  
  144.  Total complexity: twice DES; thus, hardly worth using.
  145.  
  146.  
  147.  Four-Rung Ladder-DES
  148.  
  149.  Now consider a similar construct, twice as long:
  150.  
  151.              A              B
  152.              |      k1      |
  153.              v      v       |
  154.             XOR <- DES1-----|
  155.              |              |
  156.              |      k2      |
  157.              |      v       v
  158.              |---- DES2 -> XOR
  159.              |              |
  160.              |      k3      |
  161.              v      v       |
  162.             XOR <- DES3 ----|
  163.              |              |
  164.              |      k4      |
  165.              |      v       v
  166.              |---- DES4 -> XOR
  167.              |              |
  168.              v              v
  169.              C              D
  170.  
  171.  A and B are 64-bit DES blocks; k1 through k4 are 56-bit DES keys.
  172.  A total of four DES operations process two DES blocks at double-DES
  173.  rates.  We would expect this to be both stronger than normal DES
  174.  and faster than triple-DES.
  175.  
  176.  In general, the left-leg of a ladder-DES structure is affected by
  177.  one fewer key than the right-leg.
  178.  
  179.  
  180.  Belief
  181.  
  182.  Can we "believe" in this basic structure?  Well, DES itself is
  183.  based on it.  But we do need to remember that DES also includes
  184.  seriously nonlinear data expansions and contractions around each
  185.  XOR.  Certainly expansion and contraction could be added to ladder-
  186.  DES, although this could be expensive.  (To avoid specifying
  187.  particular S-box contents, we could specify a cryptographic RNG
  188.  which would be used to permute a base S-box arrangement; this
  189.  should also avoid normal differential attacks.)  It is not clear
  190.  that the lack of expansion and contraction operations necessarily
  191.  negates the overall approach.
  192.  
  193.  
  194.  Key Reduction
  195.  
  196.  The four-rung ladder-DES construct uses four 56-bit DES keys, but
  197.  certainly a cipher would be strong enough if it had "only" a real
  198.  two-key (112-bit) keyspace.  Thus, we might consider making k3 = k1,
  199.  and k4 = k2, or perhaps, k3 = k1 and k4 = k1 XOR k2.
  200.  
  201.  On the other hand, perhaps it would be worthwhile to support
  202.  additional keys simply to avoid the necessity of showing that a
  203.  reduced key approach could never reduce strength.
  204.  
  205.  
  206.  Known-Plaintext Attack on Four-Rung Ladder-DES
  207.  
  208.  No longer do we have the advantage of knowing both the input to
  209.  and the output from XOR operations, so we can no longer gain access
  210.  to the output of particular DES operations.  Thus, the obvious
  211.  search strategy is not available.
  212.  
  213.  
  214.  Divide-And-Conquer Attack on Four-Rung Ladder-DES
  215.  
  216.  Normally we try to separate the effects of the different DES
  217.  operations, so we can "divide and conquer" each separately.
  218.  In this case, DES4 is the obvious first choice, since with the
  219.  keys k1..k3 fixed, only k4 affects the output, and then it only
  220.  affects block D.  However, unless we know the values of k1 and k2,
  221.  we don't know the input to the bottom XOR, and so apparently
  222.  cannot separate DES4 to work on it.
  223.  
  224.  
  225.  Meet-In-The-Middle Attack on Four-Rung Ladder-DES
  226.  
  227.  With four keys involved, and no obvious "middle," it is not clear
  228.  how this attack could be applied.
  229.  
  230.  
  231.  2x Four-Rung Ladder-DES
  232.  
  233.  The basic Ladder-DES construct can be expanded to cipher four
  234.  blocks at once:
  235.  
  236.              A              B         C              D
  237.              |      k1      |         |      k2      |
  238.              v      v       |         v      v       |
  239.             XOR <- DES1 ----|        XOR <- DES2 ----|
  240.              |              |         |              |
  241.              |      k3      |         |      k4      |
  242.              |      v       v         |      v       v
  243.              |---- DES3 -> XOR        |---- DES4 -> XOR
  244.              |              |         |              |
  245.              v              v         v              v
  246.              E              F         G              H
  247.  
  248.                          Re-arrange Blocks
  249.  
  250.              H              E         F              G
  251.              |      k5      |         |      k6      |
  252.              v      v       |         |      v       |
  253.             XOR <- DES5 ----|        XOR <- DES6 ----|
  254.              |              |         |              |
  255.              |      k7      |         |      k8      |
  256.              |      v       v         |      v       v
  257.              |---- DES7 -> XOR        |---- DES8 -> XOR
  258.              |              |         |              |
  259.              v              v         v              v
  260.              I              J         K              L
  261.  
  262.  This construct enciphers four DES data blocks in eight DES
  263.  operations; again, this is a speed comparable to double-DES, and
  264.  substantially faster than triple-DES.
  265.  
  266.  Ciphertext block I is now a function of every bit in plaintext
  267.  blocks A, B, C, and D, as well as every bit in keys k1, k2, k4,
  268.  and k5.  Every bit in the 64-bit I is a complex function of
  269.  480 bits.
  270.  
  271.  We could certainly afford to reduce the number of keys in these
  272.  constructs, and this might be done in any number of ways.  For
  273.  the 2x construct, for example:
  274.  
  275.       k2 := k1 XOR k3;  k4 := k3 XOR k5;
  276.       k6 := k5 XOR k7;  k8 := k7 XOR k1;
  277.  
  278.  leaving us with a need for four keys:  k1, k3, k5 and k7.  It is
  279.  also possible that the same two keys could be used in every two-
  280.  rung ladder-DES section, for a total of two keys.
  281.  
  282.  
  283.  Conclusion
  284.  
  285.  DES operations can be arranged into a "ladder-DES" constructs which
  286.  are especially-clean and familiar and seem to resist known attacks.
  287.  These constructs seem potentially stronger than normal DES and are
  288.  demonstrably faster than triple-DES.  Thus, ladder-DES could be a
  289.  reasonable candidate to replace DES.
  290.